1. Field of the Invention
The present invention generally relates to the field of distributed real-time systems. More particularly, this invention relates to a system and method for implementing priority inheritance in distributed real-time systems.
2. Description of the Prior Art
Real-time operating systems (RTOS) are those in which correctness and usefulness of the results depends not only on the logical results of computation, but also on the time at which the results are produced. Such systems may be distributed (e.g. use more than one processor, such as is shown in FIG. 1) or non-distributed (e.g. stand-alone systems). It should be understood that the level of abstraction represented in FIG. 1 also represents an environment which could include the invention and in which the meritorious effects of the invention could be achieved. It should also be understood that the illustration of a mutual exclusion (mutex) object and the depictions of operations of FIGS. 3-5 are arranged to facilitate conveyance of an understanding of the invention and no portion of any of FIGS. 1-5 is admitted to be prior art in regard to the present invention. Accordingly, these Figures have been labeled as being “Related Art”.
A typical approach to designing real-time systems requires that the system be a federation of autonomous components (100, 110, 120), having common policies and protocols to provide aggregate functionality. Each processor (140) in a single or distributed real-time system will typically host multiple applications (e.g. software modules (150), a real-time operating system (RTOS) (170) and, optionally, a middleware layer (160). Real-time applications can be developed using a client/server, dataflow, publish/subscribe or other models. To illustrate the background related to this invention, the client/server model will be used for convenience and clarity of explanation, but a skilled practitioner will be able to port the concepts to other design models.
The interaction between clients and servers involves 10 over the network (130). The term IO Channel or just Channel is frequently used when describing the passage of messages between a specific pair of distributed modules. As such, the term Channel captures the SW concept associated with Open, then Read/Write and finally Close statements. The normal tasks associated with IO, addressing, data movement, synchronization, etc, can be either included in the application or relegated to the middleware.
A typical middleware will provide capability like that described by the Object Management Group's Common Object Request Broker Architecture (CORBA). Middleware formalizes the concept of servers and extends what was originally a single processor concept to the distributed environment. It makes services provided by the RTOS, Middleware and/or Application equivalent and it supports servers being called by synchronous (client does a write then a read to await results) or asynchronous (client does write but does not await results) invocations.
Typical RTOS provide for management of the application by allocating ‘threads of control’ to the application modules and by assigning relative priority values for these threads. As threads become ready-to-run the RTOS or Scheduler will consider the relative priority of the running and ready-to-run threads. If required, the current activity (e.g. a running or ready to run thread) will preempt a currently running thread of lower priority. Because some computing activities must be completed without interruption (hereafter called serially reusable resources), RTOS provide mutex locks (200) which are often implemented as object-oriented programming “objects”. (Mutexes, however implemented, are well-understood in the art and standards for their implementation have been developed and are referred to as POSIX standards.) As illustrated in FIG. 2, these mutexes include identification (210) and state information for a locked state (220). and a held state (240), the owner of the lock (230) and operations for Seize (250) and Release (260) operations. In practice, each task requiring usage of a controlled resource applies for ownership of the mutex. Mutex processing either awards mutex ownership to the applicant thereby allowing it to use the resource or holds the applicant's thread. Release processing (260) resets ownership and, if required, promotes a held task to owner.
Client/Server connections frequently use services in chains, for example, Program A calls Program B, which calls Program C that in turn uses data from Program D. Because the RTOS and Schedulers are local to a processor, so are threads. However, middleware tends to hide the implementation details associated with multiple threads on the client and server sides, matching pairs of read/write statements and isolated tasks managed by two RTOS. As a result, developers have, for the purposes of analysis, enlarged the concept of thread and task to include all of the involved local threads and tasks. The term “Global Thread” or “Global Task” would be correct, but it is not always used.
Priority inversion (300) is an undesirable side effect of mutex and thread preemption processing. Referring to FIG. 3, consider tasks H, L and M with priority high, low and medium, respectively. Assume task L is running and it seizes resource mutex R (310), but is then interrupted as a result of the scheduler determining that Task M (320) has become ready to run. Then suppose that Task H is initiated (330) with the objective of satisfying some real-time constraint. Task H will interrupt Task M, but suppose Task H needs Mutex R. When it seizes R (340) it will be placed into R's queue (currently Task L owns Mutex R) and because H is no longer ready to run (350) the scheduler will cause Task M to resume. The problem this poses is clear; absent preemption, the Task H's delay will be Task L's locking period. With priority inversion Task H's locking period might be extended by the sum of all possible Task M execution periods, possibly an indeterminate value.
Priority inheritance (400) makes the owner of a mutex temporarily inherit the highest priority of any task being held by the mutex, but only for the period while it is actually the mutex owner. As shown in FIG. 4, when the previous example is changed to include priority inheritance, Task H, attempting to seize Mutex R, will change Task L into Task L(h) (400) (same task with temporary high priority). Task L(h) will immediately preempt Task M and proceed to completing its use of the resource. Release processing (420) will pass mutex ownership to Task H as desired, thereby eliminating the potential Task M related delays.
Effective priority inheritance also requires that the operation be applied recursively. It is possible that Task L after seizing Resource Mutex R also attempted to seize Resource Mutex R1, but was held because Task O (some other task) owned R1. To provide the recursive capability RTOS priority management services and mutex Priority Inheritance (270), local operations are developed to recognize and to respond to that condition.
In a distributed system, however, where the Task H, L and M considered previously are interpreted to be ‘Global Tasks’, priority inversion (500) can occur between processors as illustrated in FIG. 5. If Task L, running on Processor x, seizes Mutex R then invokes a remote server (520) it can be interrupted by a remote Task M (530) that may or may not require mutex R. (Even if Task M required mutex R, priority inheritance would not occur since Task L originates on a remote processor and processor y cannot raise its priority.) Task H can run on processor x (540) but when it attempts to seize Mutex R it will be held in the queue (560). In that situation locally based priority inheritance (570) will not be effective. Further, the degree of remoteness is not limited. In the client/server chaining alluded to above, Program A, B, C and D were connected. The priority inversion could occur between a Mutex in A and task interruption in D.